package com.kk.algorithm.dac;

/*
 * @Description:    汉诺塔传说 -- 分治算法
 * @Author:         Jk_kang
 * @CreateDate:     2021/2/2 0:04
 * @Param:
 * @Return:
 **/
public class HanoiTower {
    public static void main(String[] args) {
        hanoiTower (11, 'A', 'B', 'C');
        // a[i]= 2^i-1;
        System.out.println ("最终步骤数：" + count);
    }

    private static long count;

    /**
     * 汉诺塔传说 -- 分治算法
     *
     * @param num 罗盘的数量
     * @param a   第一根柱子 a
     * @param b   第二根柱子 b
     * @param c   第三根柱子 c
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        // 若只有一个盘
        if (num == 1) {
            System.out.println ("第一个盘从" + a + "->" + c);
            ++count;
        } else {
            // 如果我们有 n >= 2 情况，我们总是可以看做是两部分盘 【1.最下边的一个盘 ，2. 上面的所有盘】
            // 1. 先把最上面所有盘 A -> B ,移动过程中会经过(使用)到 C，C算是起到辅助吧
            hanoiTower (num - 1, a, c, b);
            // 2. 把最下边的盘 A -> C
            ++count;
            System.out.println ("第" + num + "个盘从" + a + "->" + c);

            // 3. 把 B塔中的所有盘 从 B -> C ，移动过程中经过(使用)到 A，A算是起到辅助吧
            hanoiTower (num - 1, b, a, c);
        }
    }
}
